1. Field of the Invention
The present invention relates to a cooperative inferring apparatus for causing a plurality of agents or a plurality of inferring agents to perform an inference in cooperation or in parallel so as to solve a problem, a cooperative inferring method thereof, a record medium recording a program thereof, and a cooperative inferring system thereof.
2. Description of the Related Art
As computer network technologies have advanced, computer systems have been changed from centralized systems of which host computers perform all processes thereof to distributed systems of which a plurality of computers that are connected through a network perform respective processes.
In a problem solving method using an artificial intelligence technology of which a problem is solved by causing a computer to imitate a problem solving process of humans, a distributed problem solving method that uses a plurality of inferring units rather than a centralized problem solving method for causing one inferring unit to perform all processes has been proposed.
In the distributed problem solving method, each inferring unit assigns an individual problem solving criterion and infers a process thereof. However, since inferred results of individual inferring units may contradict each other or a problem cannot be solved without a cooperation of other inferring units, it is preferred to cause information to be exchanged among inferring units so that the respective processes are corrected and consistently performed.
The process for exchanging information is referred to as negotiation. So far, a variety of negotiation protocols such as contract net protocol and integrated negotiation protocol have been proposed.
The contract net protocol imitates the principles of a market and proposes the process for exchanging information for assigning a task. In this case, a problem that takes place in a problem solving process and that cannot be solved by one inferring unit and a problem that can be effectively solved by another inferring are referred to as task. When an inferring unit that has a task publicizes it (this inferring unit is referred to as manager), the other inferring units (they are referred to as contractors) infer whether or not to contract with the manager to execute the task depending on their situations. When a contractor is in a situation of which it can contact with the manager for the task, it tenders for the task. Any inferring unit becomes a manager when it publicizes a task.
When a contractor tenders for a publicized task, it attaches the cost thereof. In reality, the cost is for example the current load of the contractor and the amount of time to perform the task. The publicized inferring unit compares conditions of individual contractors and accepts the bid of an inferring unit that has tendered for the task with the optimum condition. For example, when several inferring units cooperatively schedule jobs, they can transfer jobs that they cannot assign them in their time tables as tasks to other inferring units.
For details of the contract net protocol, refer to "The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver", by R. G. Smith, IEEE Transactions on Computers, Vol. 29, No. 12, pp. 1104-1113, 1980.
Next, the integrated negotiation protocol will be described. In the integrated negotiation protocol, each inferring unit operates so that the effect (profit) of each inferring unit becomes maximum (namely, economical rationality), thereby obtaining inconsistent states of inferring units and an agreement of the possibility of cooperation thereof.
In the integrated negotiation protocol, individual inferring units make plans (compromise plans) corresponding to their circumstances. Thus, a joint plan of which each plan is combined is obtained. In addition, the cost of each plan of the joint plan is calculated. A set of compromise plans (a set of negotiations) of which the effect is maximum for each inferring unit is obtained.
In this case, an example of a compromise plan is an alternative of a schedule adjustment of a meeting (such as "day 3", "day 4", and "day 7"). A set of negotiations is a set of compromise plans. Examples of set of negotiations are "days 3 and 4" and "days 4 and 7".
A compromise plan is designated "effect" as an evaluated value. When "day 3" is more convenient than "day 7", the relation of [effect of "day 3"]&gt;[effect of "day 7"] is satisfied.
With the set of negotiations, a conflicting state, a compromising state, and a cooperating state are defined. Each unit adopts the most profitable compromise plan as a plan. In other words, the "cooperating state" represents that there is of a compromise plan that both units can profitably accept. For example, a negotiation between a selling party and a buying party is effected at the initially presented price. The "compromising state" represents that there is a compromise plan that is not the best, but better than the current state. For example, in the case that the selling party slightly reduces the price of a sales item from the initially presented price, the effect is larger than the case that it is stocked. In this case, the action of which the selling party sells the sales item at a reduced price is a "compromise plan".
The "conflicting" state represents the case that there is no compromise plan and thereby a negotiation is not effected. In the case of the "conflicting state", a probability selecting means such as a dice or a lot is used to determine which of the parties is lost (mixed joint plan) and thereby rationally perform the negotiation. This is because when an agreement is not obtained, the problem is not solved and thereby the entire problem of the inference cannot be solved. Since the negotiation is probabilistically effected, one party is not continuously lost. Thus, a better result than the state that the negotiation is not effected is obtained. Consequently, negotiations in all the cooperating state, the compromising state, and the conflicting state can be performed.
In such a precondition, a local inferring unit publicizes compromise plans in the order of higher effect and agrees with the negotiating unit when a compromise plan of the negotiating unit has higher effect than one of compromise plans of the local inferring unit.
For details of the integrated negotiation protocol, refer to "Cooperation and Conflict Resolution via Negotiation Among Autonomous Agents in Non-Cooperative Domain", by G. Zlotkin and J. S. Rosenschein, IEEE Transaction on Systems, Man, and Cybernetics, Vol. 21, No. 6, pp. 1317-1324, 1991.
In the above-described related art references, it is expected that various proposals made between units allow them to be consistent. In addition, each unit performs an inference with an unspoken agreement that the latest inferred state that has been obtained through negotiations is the best way.
However, since each unit does not know the inside of other units, if a negotiation has reached a deadlock with a particular compromise plan, the content of the existing negotiation as the precondition for inferring the compromise plan may be overruled. In this case, since each unit loses the basis of the inference, each unit should retry the inference. Thus, the inference cannot be effectively performed. Particularly, in the conventional inference, assuming that various selectable options in the inferring process are branches of a tree chart, depth priority searching is performed. However, whenever a branch close to the root is overruled, the inference should be retried.
In addition, when an inference is performed with a precondition of the latest negotiating state, the range of the solution becomes narrow and thereby the probability of which the precondition is overruled becomes high. Thus, with the content of a negotiation that just precedes the latest negotiation, a better solution may be obtained. However, it is difficult to assign a criterion that represents which content of the negotiation is proper. Moreover, when an inference is retried because the preceding inference has reached a deadlock, it is not clear to distinguish substantial proposals and processes from settled agreements. Thus, since it is not clear to backtrack for the inference, the process was troublesome.
Furthermore, in the conventional negotiation protocol, since information exchange necessary for a negotiating process is mixed with information exchange used for a real negotiation, when the negotiation protocol is applied to a real problem, it is difficult to install the conventional negotiation protocol to an inferring unit. In other words, when the conventional negotiation protocol is installed to an inferring unit, a procedural process with respect to a negotiation framework such as "'start/end of a negotiation and an identification of an item to be negotiated" and a substantial process such as practical conditions of quantity and amount of money for example "quantity is 20/amount of money is 1500 yen".